If a service provider is unable to control traffic flow, it is difficult for the service provider to deliver a reliable level of service to each of its subscribers. Controlling traffic flow, including rate limiting and traffic shaping, also referred to as rate shaping, is important to make sure traffic flows smoothly through a network. A method of controlling traffic entails placing a shaper at the head of a queue. Packets are placed in the queue, and then forwarded in accordance with the shaper and a scheduling algorithm implemented in a scheduler. The scheduler typically picks the queue from which a packet is to be forwarded using a scheduling algorithm (typically a round-robin scheduling algorithm). The scheduler can only pick a queue that is enabled by the shaper. The shaper prevents the scheduler from dequeuing packets at a rate that would exceed the limits that are enforced by the shaper.
A first category of traffic shaping involves reducing burstiness so that traffic is forwarded more steadily into a network. The first category is commonly implemented using a leaky bucket algorithm. A second category of traffic shaping includes permitting bursts of a predetermined size in order to present a burst-regulated stream of traffic to the network. The second category is commonly implemented using a token bucket algorithm. Each of these tools has different capabilities and results in output streams with different characteristics.
The leaky bucket algorithm turns a bursty stream of packets into a stream of more equally spaced packets. With the leaky bucket algorithm, a stream of packets is placed into a queue controlled by a leaky bucket shaper. Over time, the shaper accumulates tokens for sending packets. When the shaper has accumulated sufficient tokens to send the packet at the head of the queue, the scheduler may send the packet. However, when a packet arrives at the queue after an idle period, i.e., a period when no packets are in the queue, the shaper must accumulate tokens before the packet is sent, thereby causing the packet to be delayed. This delay is proportional to the packet size. The bigger the size of the packet, the higher the delay.
The token bucket rate-limiting algorithm enforces a long-term average transmission rate while permitting bounded bursts. Using this approach, a token generator generates tokens in advance of receiving a packet. This eliminates the delay that occurs with the leaky bucket algorithm after an idle period. However, the accumulated tokens may be used to send a series of small packets, when one small packet does not use all of the accumulated tokens. This increases the burstiness of the traffic.
In view of the desire to control traffic flow, what is needed is a new traffic shaping tool that does not delay traffic after idle periods in order to accumulate tokens before sending a received packet and, at the same time, does not accumulate tokens while idle, so that a plurality of small packets received after idle periods are sent in a steady stream, rather than a large burst.